Complejidad – Programación (página 2)

Partes: 1, 2

Funciones recursivas
Establecer la ecuación de recurrencia:
Complejidad en el caso base
Complejidad en el caso recursivo
Expandir la complejidad en el caso base en función del número de llamadas recursivas hechas
Encontrar el número de llamadas necesarias para estar en el caso base

Ejemplo: Factorial
Ecuación de recurrencia:
T(n) = a, n = 0
T(n) = b + T(n-1), n > 0
Expandir en el caso recursivo:

Ejemplo: Factorial
T(n) = kb + T(n-k)
Para eliminar la dependencia de T(), escoger k tal que estamos en el caso base
Si k=n, T(n-k) = T(0) = a
Si substituimos k=n en la expresión, obtenemos T(n) = bn + a
¿Notación asintótica?

Ejemplo: Búsqueda binaria
funcion BB(V:vector; i,d,k:natural)
devuelve booleano
si (i = d) entonces
devuelve (V[i] = k);
sino si (V[(i+d)/2] < k) entonces
devuelve BB(V, (i+d)/2 + 1, d, k);
sino
devuelve BB(V, i, (i+d)/2, k);
fsi
ffuncion

Ejemplo: Búsqueda binaria
Ecuación de recurrencia (medida n=d – i):
T(n) = a, n = 0
T(n) = b + T(n/2), n > 0
Expandir en el caso recursivo:

Ejemplo: Búsqueda binaria
T(n) = kb + T(n/2k)
Para eliminar la dependencia de T(), escoger k tal que estamos en el caso base
Problema: n/2k = 0 => 2k = ?
Idea: escoger n/2k = 1 ? k = log(n)
T(n) = b*log(n) + T(1) = b*log(n) + b + a
¿Notación asintótica?

Ejemplo: Mergesort
Medida: n = D – E
Depende de la complejidad de Combina
Los bucles de Combina se repiten un número de veces igual al número total de elementos de V1 y V2
Ecuación de recurrencia:
T(n) = a, n = 0
T(n) = b + c*n + 2T(n/2)

Ejemplo: Mergesort

n/2k = 1 ? k = log(n)
T(n) = bn + cnlog(n) + an
¿Notación asintótica?

Un experimento
Ordenar mil millones de elementos
Procesador con frecuencia 1GHz
Tiempo de ejecución aproximado
Bubble (Insertion, Selection) Sort: O(n2)
Mergesort: O(nlog(n))
log(109) ? 30
109 segundos ? ¡32 años!

Ejemplo: Quicksort
Caso mejor: como Mergesort
Caso peor: ¡como Bubble Sort!
Caso promedio: como Mergesort